package com.xjj.dbfs;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class H0051NQueens {

    private List<List<String>> result = new ArrayList<>();

    private Set<Integer> xSubY = new HashSet<>();

    private Set<Integer> xAddY = new HashSet<>();

    private Set<Integer> x = new HashSet<>();

    public List<List<String>> solveNQueens(int n) {
        // n行n列全走一遍
        dfs(0, n, new ArrayList<>());
        return result;
    }

    private void dfs(int row, int n, List<Integer> tmp) {
        if (row >= n) {
            result.add(build(n, tmp));
            return;
        }
        for (int i = 0; i < n; i++) {
            // 行递增不用判断,所以要判断仨方向,列,左对角,右对角
            if (!xSubY.contains(i - row) && !xAddY.contains(i + row) && !x.contains(i)) {
                tmp.add(i);
                xSubY.add(i - row);
                xAddY.add(i + row);
                x.add(i);

                dfs(row + 1, n, tmp);

                // 还原
                tmp.remove(tmp.size() - 1);
                xSubY.remove(i - row);
                xAddY.remove(i + row);
                x.remove(i);
            }
        }
    }


    private List<String> build(int n, List<Integer> results) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int result = results.get(i);
            String str = "";
            for (int j = 0; j < n; j++) {
                if (j ==  result) {
                    str += "Q";
                } else {
                    str += ".";
                }
            }
            list.add(str);
        }
        return list;
    }
}
